package com.future;

/**
 * Description: 334. ��������Ԫ������ (�ɲο�300. �����������)
 * ����һ����������?nums ���ж�����������Ƿ���ڳ���Ϊ 3 �ĵ��������С�
 * <p>
 * ���������������Ԫ���±� (i, j, k)?������ i < j < k ��ʹ��?nums[i] < nums[j] < nums[k] ������ true �����򣬷��� false ��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/increasing-triplet-subsequence
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/11 10:59
 */
public class Solution_334 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5};
        nums = new int[]{5, 4, 3, 2, 1};
        nums = new int[]{2, 1, 5, 0, 4, 6};
        nums = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        System.out.println(increasingTriplet(nums));
        System.out.println(increasingTriplet_v2(nums));
    }

    /**
     * ����
     *
     * @param nums
     * @return
     */
    public static boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int N = nums.length;
        int[] dp = new int[N];
        dp[0] = 1;
        for (int i = 1; i < N; i++) {
            int max = 0;
            int val = nums[i];
            for (int j = 0; j < i; j++) {
                if (nums[j] < val) {
                    max = Math.max(max, dp[j]);
                }
            }
            max++;
            if (max >= 3) {
                return true;
            }
            dp[i] = max;

        }
        return false;
    }

    public static boolean increasingTriplet_v2(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int N = nums.length;
        int[] dp = new int[N];
        dp[0] = nums[0];
        int R = 0;
        for (int i = 1; i < N; i++) {
            int val = nums[i];
            int index = nearestIndex(dp, val, 0, R);
            if (index >= 2) {
                return true;
            }
            R = Math.max(R, index);
            dp[index] = val;
        }
        return false;
    }

    private static int nearestIndex(int[] dp, int target, int l, int r) {
        int res = l;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (dp[m] < target) {
                l = m + 1;
                res = l;
            } else {
                r = m - 1;
            }
        }
        return res;
    }


}
